home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / FROMUTS / WORDCHECK / !WordChk / README < prev    next >
Text File  |  1992-03-17  |  13KB  |  365 lines
  1. Word Check Module (Formally SpellChk)
  2. ==================
  3.  
  4. RiscOS 3 version 0.03 © Geoff. Lane. Mar 1992
  5. Internet: zzassgl@uts.mcc.ac.uk
  6. Janet   : zzassgl@uk.ac.mcc.uts
  7.  
  8. (The information given here may not exactly match the current state of
  9. the module.)
  10.  
  11.  
  12. Introduction
  13. ------------
  14.  
  15. This implements a word spelling check module for British/American
  16. technical English (with a selection of Arc specific words added for
  17. good luck) or other (unsupplied)languages. It is based on a
  18. description in Chapter 13 of "Programming Pearls" by Jon Bentley (ISBN
  19. 0-201-10331-1) of a clever algorithm devised by Doug McIlroy in 1978.
  20.  
  21. Many RiscOS based word processors contain a spelling checker; each has
  22. its own word list and interface.  These checkers are impossible to use
  23. outside the application.  For each application there will be one or
  24. more large diictionary files each unique to the application.  If a
  25. standard interface were created using SWIs it would be possible of one
  26. module to provide  Word check function to all applications that
  27. required such a facility. If an application could rely on a Word
  28. check module being available then the application would be smaller.
  29. The facilities provided within this module are a first attempt to
  30. define such an interface.
  31.  
  32. This program was created and tested on a 2M A5000 machine running
  33. RiscOS 3.  The compiler used was Norcroft C version 3.0. The shared
  34. library version used was 3.87 (I haven't included any RMEnsure
  35. commands in the !Boot or !Run files - I'm not aware of any version
  36. dependancies) If you don't have the C library in ROM then you should
  37. edit the files to check for and load the shared library.
  38.  
  39.  
  40.  
  41. Algorithm
  42. ---------
  43.  
  44. The algorithm allows a dictionary to be highly compressed by encoding
  45. each word as a unique 32 bit number.  The resulting list of numbers is
  46. sorted and then a table of differences is created.  This table of 16
  47. bit numbers is included in the module.  To find a word in the table
  48. you encode the word and then see if it is possible to generate the
  49. same value by summing the contents of the table - if you get a match
  50. then the word is valid. (Of course you have to chose the encoding
  51. algorithm quite carefully to ensure that the vast majority (in this
  52. case only 19 words hash to the same value) of words translate to
  53. unique numbers and the differences between each pair of sorted numbers
  54. is always less than 32K.) Thus a module of about 71K bytes can be used
  55. to check the spelling of about 32000 different words.
  56.  
  57.  
  58. Building Word Lists
  59. -------------------
  60.  
  61. The word lists were created from a number of sources...
  62.  
  63.  * Take 1.5 Gbytes of Netnews.
  64.  * Take the Brown University Corpus of English Usage.
  65.  * Take the Unix online manual pages.
  66.  * Take the RiscOS help text.
  67.  
  68. Delete the non-alphabetics, sort and delete duplicates. From this you
  69. obtain a huge list of words plus a lot of junk. You pass this list
  70. through a standard spelling checker and then check the reject list for
  71. words that are useful but not accepted.
  72.  
  73.  
  74. Features
  75. --------
  76.  
  77. * Installed as a module.
  78.  
  79. * Large dictionary but small memory requirements. (To an old BBC B
  80. programmer the fact that I can even contemplate dedicating over 64K of
  81. memory to a utility is slightly obsene.)
  82.  
  83. * General purpose. The spelling check is available to any program (or
  84. module) and not restricted to a particular application.
  85.  
  86. * Multiple language support. British English, {work in progress
  87. American English}  are supplied. The language to be used in a given
  88. run can be selected by command. The (changable) default is British
  89. English.
  90.  
  91. * Fairly fast. On an A5000 the current version could check about 500
  92. words/second when running a test program within a Task Window and
  93. about 620 wps running "native". (It is interesting to know that in the
  94. description of the algorithm in the book mentioned above the speed is
  95. described as about 170 wps on a VAX 11/750 - this was considered fast
  96. at the time the book was written! The VAX version was just under 64K
  97. in size - the dictionary was a bit smaller.)
  98.  
  99.  
  100. Bugs and/or Misfeatures
  101. -----------------------
  102.  
  103. (It's not as bad as it looks.  The module is only intended to
  104. implement basic spelling checks; clever preprocessing should be done
  105. by the application program and not set in stone within the module.)
  106.  
  107. * Does not perform pre- or post-fix stripping.
  108.  
  109. * Can't cope with many plurals (special case of the lack of post-fix
  110. stripping.)
  111.  
  112. * Complains about what it believes to be uncorrectly capitallised
  113. words (Many "standard" capitallisations are encoded in the word list.)
  114.  
  115. * Does not check single character words (i,a,...)
  116.  
  117. * Currently not possible to supply a personal dictionary to be added
  118. to the standard pre-loaded dictionary.
  119.  
  120. * The algorithm used can miss a small proportion of bad spellings.
  121. (About 1 in 1000 misWorded words will get through.)  This is a result
  122. of the way that the words are encoded -- the error rate could be
  123. reduced at the cost of a larger word table but then the major
  124. advantage of having a small module size (and thus speed) are lost.
  125.  
  126. * Anagram solver will be limited and quite slow.
  127.  
  128. * Word finder is limited and quite slow.   It operates by using a
  129. brute force search using all possible words that may exist which fit
  130. the supplied partial word. Most of the possibilities are incorrect
  131. spellings so it pushes the checking algorithm to it's limits and thus
  132. reports more incorrect words than it should.
  133.  
  134. * Difficult to use as a spelling corrector.  The module cannot suggest
  135. close matches to a supplied word as the encoding algorithm generates
  136. unrelated hash values for similar words; in addition the original word
  137. list is not available to the module at run-time.
  138.  
  139.  
  140. Configurable Bits
  141. -----------------
  142.  
  143. * The default dictionary language used when the module is loaded can
  144. be changed by altering the "WordChk$DefLang" environment variable in
  145. both !Run and !Boot files.
  146.  
  147. * New languages can be installed by adding the encoded dictionaries to
  148. the "Languages" sub-directory.  They can then be specified as the
  149. default language or loaded with the *WordLoad command. 
  150.  
  151.  
  152. Command Interface
  153. -----------------
  154.  
  155. This allows a single word  entered from the command line to be checked
  156. against the current dictionary.
  157.  
  158.   *WordCheck <word>
  159.   ok/unknown
  160.  
  161. {Work in progress} This treats the supplied word as an anagram and
  162. tries to rearrange it into words that are found in the current
  163. dictionary.
  164.  
  165.   *WordGram <word>
  166.  
  167. This takes a word with missing characters (indicated by ?'s in the
  168. string) and tries to find matching words in the current dictionary.
  169.  
  170.   *WordFind <partial word>
  171.  
  172. This loads a new language as the current dictionary. At the moment
  173. valid languages are "British" {work in progress, "American" and
  174. "Technical".}
  175.  
  176.   *WordLoad <language>
  177.  
  178.  
  179. Program Interface
  180. -----------------
  181.  
  182. The module provides the following SWIs...
  183.  
  184. "WordCheck_Word"
  185.  
  186. Input
  187.  
  188.   R0   pointer to string to test (null byte terminated character
  189.        string as generated by BASIC V or C)
  190.  
  191. Output
  192.  
  193.   R0   preserved
  194.   R1   returns boolean (-1/TRUE or 0/FALSE)
  195.  
  196. BASIC Example
  197.  
  198.   SYS "WordCheck_Word","syzygy" TO ,valid%
  199.  
  200.   returns valid% = -1/TRUE (honest)
  201.  
  202. whereas
  203.  
  204.   SYS "WordCheck_Word","pointer" TO ,valid%
  205.  
  206.   returns valid% = 0/FALSE (shame!)
  207.  
  208.  
  209. "WordCheck_Find"
  210.  
  211. Input
  212.  
  213.   R0   pointer to string to test with up to three '?' characters indicating
  214.        unknown characters (null byte terminated character string as
  215.        generated by BASIC V or C) To obtain further possible matches use
  216.        "WordCheck_FindNext"
  217.  
  218. Output
  219.  
  220.   R0   preserved
  221.   R1   returns first found word or null string if nothing found.
  222.  
  223. BASIC Example
  224.  
  225.   SYS "WordCheck_Find","te?t" TO ,match$
  226.  
  227.   returns match$ = "teat"
  228.  
  229.  
  230. "WordCheck_FindNext"
  231.  
  232. Output
  233.  
  234.   R1   returns next matching word or null string if nothing found.
  235.  
  236. BASIC Example
  237.  
  238.   This assumes that "WordCheck_Find" has been called with an initial
  239.   partial word of "te?t".
  240.  
  241.   SYS "WordCheck_FindNext" TO ,match$
  242.  
  243.   returns match$ = "tent"
  244.  
  245.   Further matches can be obtained by more calls to "WordCheck_FindNext"
  246.   until the end of all possible matches is indicated by the return of a null
  247.   string.  For instance,in BASIC, to find all matches use code similar to...
  248.  
  249.         SYS "WordCheck_Find","te?t" TO ,m$
  250.         WHILE m$ <> ""
  251.           PRINT m$
  252.           SYS "WordCheck_FindNext" TO ,m$
  253.         ENDWHILE
  254.  
  255.  
  256. "WordCheck_Load"
  257.  
  258. Input
  259.  
  260.   R0   pointer to string holding language name to load (null byte 
  261.        terminated character string as generated by BASIC V or C.) The
  262.        corresponding named language file must be present in the Languages
  263.        sub-directory within !WordChk.
  264.  
  265. Output
  266.  
  267.   R0   preserved
  268.   R1   returns -1/TRUE if successful otherwise 0/FALSE.
  269.  
  270. BASIC Example
  271.  
  272.   SYS "WordCheck_Load","British" TO ,ok%
  273.  
  274.   returns ok% = -1/TRUE if language "British" has been loaded.
  275.   returns ok% = 0/FALSE if failed to load new language.
  276.  
  277.  
  278. Building New Dictionary Files
  279. -----------------------------
  280.  
  281. [[[ NOT IN THIS VERSION ]]]
  282.  
  283. A program, BuildDict, is provided which can create new encoded
  284. dictionary files from word lists.  These files can then be loaded into
  285. the module.  To create a new dictionary you need to do the following...
  286.  
  287.   * Gather a word list.  There must be at least 256 words in the list
  288.     and there will probably have to be many more words in order that
  289.     the difference between the hash values is always < 64K.  There
  290.     should not be more than 33000 words in the list.
  291.  
  292.   * Delete single character words and ensure that there are no
  293.     leading or trailing spaces or tabs at the end of the words. 
  294.     There should only be one word per line.
  295.                            
  296.   * Sort the list (not essential for BuildDict but needed for
  297.     following step.)
  298.  
  299.   * Delete duplicate words.
  300.  
  301.   * Place the file in the WordLists sub-directory of !WordChk.
  302.  
  303.   * Run the BuildDict program.  This will create, if successful, an
  304.     encoded dictionary file in the Languages sub-directory.  There are
  305.     a number of possible fatal errors that may occur during
  306.     processing.
  307.  
  308.   * Change the WordChk$DefLang value set in !Boot and !Run to make
  309.     your new language the default or use the *WordLoad command to
  310.     load the new language into a running module.
  311.  
  312. The hash algorithm has been optimised for UK/US English.  It not be
  313. suitable for other languages.  A future version of !WordChk may
  314. include a means to alter and re-optimise the hash algorithm if
  315. necessary for each language to be loaded.
  316.  
  317. Foreign Languages
  318. -----------------
  319.  
  320. True spelling checkers for foreign languages are complicated by the
  321. fact that most of them care about the 'sex' of the words.  Some of
  322. them are so regular that native writers rarely make spelling errors
  323. other than simple 'typing' errors ie transposition of characters. Some
  324. languages insist on strange characters that do not appear on the
  325. keyboard.  The Arc copes quite well with the strange characters for
  326. languages such as french and German.  Languages such as Esperanto are
  327. not so well provided for as the accents appear on unexpected
  328. characters and special provision would have to be given to defining
  329. them.
  330.  
  331. In any case WordChk is just a word checker and not a full spelling
  332. checker (the difference is that one just tries to match a word to one
  333. in a list, the other attempts to manipulate the word in various ways
  334. to attempt to find the root.) 
  335.         
  336.         British         {word list being repaired}
  337.         American        {word list being repaired}
  338.         Computing       {work in progress}
  339.         Hacking         {work in progress}
  340.         French          need smaller word list!
  341.         German          need word list.
  342.         Italian         need word list.
  343.         Esperanto       can't display accented characters from default font.
  344.         Latin           need word list (getting a bit weird here?)
  345.  
  346.  
  347.  
  348. =====================================================================
  349.  
  350. The legal bit: I don't care what kind of ...ware it is called but I
  351. retain copyright on the code and encoded dictionary table used in this
  352. particular RiscOS implementation of the spelling checker algorithm.
  353. You can distribute version 0.03 of the WordCheck module and
  354. associated files as far and wide as you wish so long as this README
  355. file is also distributed with the module and hash file. You may
  356. include the !WordChk application (or just the language, Wordchk
  357. module and README files) within another application that makes use of
  358. its facilities. If you paid money (other than a small amount for disc
  359. duplication and postage) for these files then you've been ripped off.
  360.  
  361. As noted above, this code is in alpha test and you take your own
  362. chances with bugs, spelling errors etc.
  363.  
  364. ======================================================================
  365.